Some applications of Description Logic (DL) ontologies combine complete information (e.g., stemming from relational databases) with incomplete, open-world knowledge. Several research efforts in the last years have advocated closed predicates, which are predicates whose extension is interpreted as complete, as a suitable way to leverage partial completeness within the standard open-world semantics of DLs. These works have also studied the data complexity of query answering in the presence of closed predicates, which is generally intractable. In this paper we contribute to the understanding the combined complexity of the problem, by establishing tight complexity results for a range of DLs and query answering problems. In summary, our results show that consistency testing and instance query answering in the presence of closed predicates are feasible in NP even for rich dialects of the DL-Lite family; this is the lowest complexity that could be expected. For EL, in contrast, they are EXPTIME-complete, thus as hard as for ALC and some of its extensions. If unions of conjunctive queries (UCQs) are considered, the picture is even bleaker: we can show 2EXPTIME-hardness even for DL-Lite_R and EL. This is in sharp contrast to the NP-upper bound in the standard setting without closed predicates, and coincides with known upper bounds for much richer DLs. We note that our results imply 2EXPTIME-hardness of query answering in ALCO for the standard setting, where all predicates are interpreted under the open-world semantics.

In many scenarios, complete and incomplete information coexist. For this reason, the knowledge representation and database communities have long shown interest in simultaneously supporting the closed- and the open-world views when reasoning about logic theories. Here we consider the setting of querying possibly incomplete data using logic theories, formalized as the evaluation of an ontology-mediated query (OMQ) that pairs a query with a theory, sometimes called an ontology, expressing background knowledge. This can be further enriched by specifying a set of closed predicates from the theory that are to be interpreted under the closed-world assumption, while the rest are interpreted with the open-world view. In this way we can retrieve more precise answers to queries by leveraging the partial completeness of the data. The central goal of this paper is to understand the relative expressiveness of OMQ languages in which the ontology is written in the expressive Description Logic (DL) ALCHOI and includes a set of closed predicates. We consider a restricted class of conjunctive queries. Our main result is to show that every query in this non-monotonic query language can be translated in polynomial time into Datalog with negation under the stable model semantics. To overcome the challenge that Datalog has no direct means to express the existential quantification present in ALCHOI, we define a two-player game that characterizes the satisfaction of the ontology, and design a Datalog query that can decide the existence of a winning strategy for the game. If there are no closed predicates, that is in the case of querying a plain ALCHOI knowledge base, our translation yields a positive disjunctive Datalog program of polynomial size. To the best of our knowledge, unlike previous translations for related fragments with expressive (non-Horn) DLs, these are the first polynomial time translations.

Some applications of Description Logic (DL) ontologies combine complete information (e.g., stemming from relational databases) with incomplete, open-world knowledge. Several research efforts in the last years have advocated closed predicates, which are predicates whose extension is interpreted as complete, as a suitable way to leverage partial completeness within the standard open-world semantics of DLs. These works have also studied the data complexity of query answering in the presence of closed predicates, which is generally intractable. In this paper we contribute to the understanding the combined complexity of the problem, by establishing tight complexity results for a range of DLs and query answering problems. In summary, our results show that consistency testing and instance query answering in the presence of closed predicates are feasible in NP even for rich dialects of the DL-Lite family; this is the lowest complexity that could be expected. For EL, in contrast, they are EXPTIME-complete, thus as hard as for ALC and some of its extensions. If unions of conjunctive queries (UCQs) are considered, the picture is even bleaker: we can show 2EXPTIME-hardness even for DL-Lite_R and EL. This is in sharp contrast to the NP-upper bound in the standard setting without closed predicates, and coincides with known upper bounds for much richer DLs. We note that our results imply 2EXPTIME-hardness of query answering in ALCO for the standard setting, where all predicates are interpreted under the open-world semantics. This singles out nominals as a previously unidentified source of complexity when answering queries over expressive DLs. Despite these negative results, we can still identify several useful classes of queries for which the increase in hardness is not as drastic, and the combined complexity of query answering remains between NP and coNEXPTIME.

In the context of ontology-based data access with description logics (DLs), we study ontology-mediated queries in which selected predicates can be closed (OMQCs). In particular, we contribute to the classification of the data complexity of such queries in several relevant DLs. For the case where only concept names can be closed, we tightly link this question to the complexity of surjective CSPs. When also role names can be closed, we show that a full complexity classification is equivalent to classifying the complexity of all problems in coNP, thus currently out of reach. We also identify a class of OMQCs based on ontologies formulated in DL-LiteR that are guaranteed to be tractable and even FO-rewritable.

When answering queries in the presence of ontologies, adopting the closed world assumption for some predicates easily results in intractability. We analyze this situation on the level of individual ontologies formulated in the description logics DL-Lite and EL and show that in all cases where answering CQs with (open and) closed predicates is tractable, it coincides with answering CQs with all predicates assumed open. In this sense, CQ answering with closed predicates in inherently intractable. Our analysis also yields a dichotomy between AC0 and coNP for CQ answering in DL-Lite and a dichotomy between PTime and coNP for EL. Interestingly, the situation is less dramatic in the more expressive description logic ELI, where we find ontologies for which CQ answering is in PTime, but does not coincide with CQ answering where all predicates are open.